Search results for "Logical programming"
showing 4 items of 4 documents
Padding and the expressive power of existential second-order logics
1998
Padding techniques are well-known from Computational Complexity Theory. Here, an analogous concept is considered in the context of existential second-order logics. Informally, a graph H is a padded version of a graph G, if H consists of an isomorphic copy of G and some isolated vertices. A set A of graphs is called weakly expressible by a formula ϕ in the presence of padding, if ϕ is able to distinguish between (sufficiently) padded versions of graphs from A and padded versions of graphs that are not in A.
Flexible pattern discovery with (extended) disjunctive logic programming
2005
The post-genomic era showed up a wide range of new challenging issues for the areas of knowledge discovery and intelligent information management. Among them, the discovery of complex pattern repetitions in string databases plays an important role, specifically in those contexts where even what are to be considered the interesting pattern classes is unknown. This paper provides a contribution in this precise setting, proposing a novel approach, based on disjunctive logic programming extended with several advanced features, for discovering interesting pattern classes from a given data set.
Run-time profiling of functional logic programs
2005
In this work, we introduce a profiling scheme for modern functional logic languages covering notions like laziness, sharing, and non-determinism. Firstly, we instrument a natural (big-step) semantics in order to associate a symbolic cost to each basic operation (e.g., variable updates, function unfoldings, case evaluations). While this cost semantics provides a formal basis to analyze the cost of a computation, the implementation of a cost-augmented interpreter based on it would introduce a huge overhead. Therefore, we also introduce a sound transformation that instruments a program such that its execution—under the standard semantics—yields not only the corresponding results but also the a…
Fast narrowing-driven partial evaluation for inductively sequential programs
2005
Narrowing-driven partial evaluation is a powerful technique for the specialization of (first-order) functional and functional logic programs. However, although it gives good results on small programs, it does not scale up well to realistic problems (e.g., interpreter specialization). In this work, we introduce a faster partial evaluation scheme by ensuring the termination of the process offline . For this purpose, we first characterize a class of programs which are quasi-terminating , i.e., the computations performed with needed narrowing—the symbolic computation mechanism of narrowing-driven partial evaluation—only contain finitely many different terms (and, thus, partial evaluation termi…